#include "List.cpp"

//给你单链表的头指针 head 和两个整数left 和 right ，其中left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

// 翻转k个元素,返回新链
ListNode* reverse(ListNode* head,int k) {
    ListNode* newHead = (ListNode*) malloc(sizeof(ListNode));
    ListNode* p = head;
    newHead->next = NULL;
    for (int i = 0; i < k; ++i) {
        ListNode* q = p->next;
        p->next = newHead->next;
        newHead->next = p;
        p = q;
    }
    return newHead->next;
}

ListNode* reverseBetween(ListNode* head, int left, int right){
    ListNode* newHead = (ListNode*) malloc(sizeof(ListNode));
    newHead->next = head;
    // pre为left-1的位置
    ListNode* pre = newHead;
    for (int i = 1; i < left; ++i) {
        pre = pre->next;
    }
    // next为right+1的位置
    ListNode* next = pre;
    for (int i = 0; i < right-left+2; ++i) {
        next = next->next;
    }
    // split为right的位置,pre原来为left反转后变为right
    ListNode* split = pre->next;
    // 链接left-1和left
    pre->next = reverse(pre->next,right-left+1);
    // 链接right和right+1
    split->next = next;
    return newHead->next;
}
int main() {
    int number[] = {1, 2,3,3,4,4};
    List list = CreateListByArray(number, ARRAY_SIZE(number));
    List newList = reverseBetween(list,2,5);
    PrintList(newList);
}
